(I) We exhibit a set of 23 points in the plane that has dilation at least$1.4308$, improving the previously best lower bound of $1.4161$ for theworst-case dilation of plane spanners. (II) For every integer $n\geq13$, there exists an $n$-element point set $S$such that the degree 3 dilation of $S$ denoted by $\delta_0(S,3) \text{ equals} 1+\sqrt{3}=2.7321\ldots$ in the domain of plane geometric spanners. In thesame domain, we show that for every integer $n\geq6$, there exists a an$n$-element point set $S$ such that the degree 4 dilation of $S$ denoted by$\delta_0(S,4) \text{ equals } 1 + \sqrt{(5-\sqrt{5})/2}=2.1755\ldots$ Theprevious best lower bound of $1.4161$ holds for any degree. (III) For every integer $n\geq6 $, there exists an $n$-element point set $S$such that the stretch factor of the greedy triangulation of $S$ is at least$2.0268$.
展开▼
机译:(I)我们在飞机上展示出23个点的集合,其膨胀至少为$ 1.4308 $,从而改善了先前最差的平面扳手膨胀的最佳下限$ 1.4161 $。 (II)对于每个整数$ n \ geq13 $,都存在一个$ n $元素点集$ S $,使得$ S $的3级膨胀由$ \ delta_0(S,3)\ text {表示}在平面几何扳手的范围内为1+ \ sqrt {3} = 2.7321 \ ldots $。在相同的域中,我们显示出,对于每个整数$ n \ geq6 $,都存在一个$ n $元素点集$ S $,使得$ S $的4级膨胀表示为$ \ delta_0(S,4) \ text {等于} 1 + \ sqrt {(5- \ sqrt {5})/ 2} = 2.1755 \ ldots $ $ 1.4161 $的上一个最佳下限在任何程度上都成立。 (III)对于每个整数$ n \ geq6 $,存在一个$ n $元素点集$ S $,这样贪婪的三角剖分$ S $的拉伸因子至少为$ 2.0268 $。
展开▼